 /*
        旋转之后，把一个有序数组变为两个有序数组
        并且第二个有序数组的最大值，一定是小于等于第一个有序数组的最小值
        因此，最小值应该在第二个有序数组的最左边
        利用二分查找的思想，可以把第一个有序数组快速跳过去，因为最小值一定不在第一个有序数组中
        如果有重复元素，可能出现mid 和right所指的值相等的情况，让右边界左移
        */
class Solution {
public:
    int minNumberInRotateArray(vector<int> array) {
     int left=0;
        int right=array.size()-1;
        while(right>left)
        {
            int mid=(right+left)/2;
            if(array[mid]>array[right]) //mid所指的值一定不在第二个有序数组中，
                left=mid+1;//把mid之前值的跳过
            else if(array[mid]<array[right]) //最小值应该在mid所指位置之前
                right=mid;
            else
                right--;
        }
        return array[left];
    }

};